The synopsis "Matrix Algebra" appearing on pages 1090-1097 of Chapter 37 of the fourth edition of REFERENCE DATA FOR RADIO ENGINEERS published by International Telephone and Telegraph Corporation, 67 Broad Street, New York 4, N.Y. is hereby included herein by reference. Chain-serial operation, insofar as matrix multiplication is concerned, can be sustained in two forms. In a first form of chain-serial matrix multiplication, an m row by n column original matrix is continuously updated by using it as the left hand multiplicand term in each of a succession of matrix multiplications with a right hand multiplier term that is the next one of a succession of n row by n column matrices. In a second form of chain-serial matrix multiplication, an n row by m column original matrix is continuously updated by using it as the right hand multiplier term in each of a succession of matrix multiplications with a left hand multiplicand term that is the next one of a succession of n row by n column matrices. Each successive matrix multiplication in the first form of chain-serial operation can be described by the matrix equation (a.sub.ij).multidot.(b.sub.ij)=(c.sub.ij) written more explicitly as follows: ##EQU1## In the matrix equation just above ##EQU2## where i and j are the numbers of the row and of the column respectively of each element in the (a.sub.ij), (b.sub.ij) and (c.sub.ij) matrices. Note that (b.sub.ij) is a square matrix, having n rows and n columns. The matrices (a.sub.ij) and (c.sub.ij) have m rows and n columns; they may be square with m equal to n, or they may not be.
Each successive matrix multiplication in the second form of chain serial operation can be described by the matrix equation (d.sub.ij).multidot.(e.sub.ij)=(f.sub.ij) written more explicitly as follows: ##EQU3## In the matrix equation just above ##EQU4## where i and j are the numbers of the row and of the column respectively of each element in the (d.sub.ij), (e.sub.ij) and (f.sub.ij) matrices. Note that (d.sub.ij) is a square matrix, having n rows and n columns. The matrices (e.sub.ij) and (f.sub.ij) may be square or may not be.
It is known to those familiar with matrix algebra that the product of the transposes of two square matrices transposes to the product of the two matrices multiplied in reverse order from their transposes. That is, (a.sub.ij).multidot.(b.sub.ij) is the transpose of (b.sub.ji).multidot.(a.sub.ji), where (b.sub.ji) is the transpose of (b.sub.ij) and where (a.sub.ji) is the transpose of (a.sub.ij). Accordingly, each step of matrix multiplication to be done in one of the first and second forms of chain-serial multiplication can alternatively be done in the other of those forms by transposing the matrices entering the reverse-order matrix multiplication and transposing the resulting matrix product. One can identify (a.sub.ji) with (e.sub.ij) and can identify (b.sub.ji) with (d.sub.ij). Then (c.sub.ij)) equals (f.sub.ji), the transpose of (f.sub.ij). While the pipeline circuitry in a chain-serial matrix multiplier may be designed particularly to suit one of the two forms of chain-serial matrix multiplication that is self-sustaining, it can be operated so as to provide the other form of chain-serial multiplication, by transposing rows and columns of the matrices involved in each matrix multiplication and by performing that multiplication in reverse order, then transposing the result.
In chain-serial matrix multipliers that embody the invention in various of its aspects, the multiplications of pairs of elements involved in the matrix multiplication are (except possibly for trivial multiplications) performed by a single multiplier. First and second streams of matrix elements are supplied to the multiplier and an ensuing accumulator, which together perform pipelined calculation of elements of the product matrix. The first stream of matrix elements is generated by scanning a first matrix as stored temporarily in and read subsequently from a first memory. This scanning may be done in row major order (i.e., by rows of elements) or in column major order (i.e., by columns of elements). The second stream of matrix elements is generated by scanning a second matrix as stored temporarily in and read subsequently from a second memory in the opposite order that said first matrix is scanned.
Where desired, transposition of the first and second matrices is easily arranged for, by transposing the order the first and second memories are written. Owing to the fact that matrices may be so easily transposed in the operation of the chain-serial matrix multipliers of the invention, a general term referring to a row or a column of a matrix is convenient to have in claiming these chain-serial matrix multipliers. Accordingly, a "line" of a matrix refers to a row of a matrix the element samples of which flow in row major order through a pipeline; and a "line" of a matrix also refers to a column of a matrix the element samples of which flow in column major order through a pipeline.
A type of memory that is convenient to use in pipelined operations involving arrays of data, such as those involved in finite-impulse-response filtering in one or more dimensions, is so-called "serial memory". Serial memory comprises a plurality of clocked delay elements, connected one after the other in cascade connection to form a tapped delay line. Each delay element exhibits a one clock interval delay between its input and output ports and provides for temporary storage of a respective sample. A multiplexer selectively connects to the input port of the first delay element in the cascade connection (i.e., the initial tap of the delay line) either a sample being written into the serial memory or a sample supplied from the output port of the last delay element in the cascade connection. The latter selection by the multiplexer provides for a circulating delay line, or ring connection of the delay elements, which sustains continuing storage of the samples written into the serial memory. Samples may be read from the serial memory at any tap along the tapped delay line (e.g., the initial tap or the final tap).